package leetcode71_80;

import org.junit.Test;

/**
 * @author shhjiang_001
 * @create 2020-06-23 19:33
 */

        /*
        给定一个二维网格和一个单词，找出该单词是否存在于网格中。
        单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
        同一个单元格内的字母不允许被重复使用。
        示例:
        board =
        [
        ['A','B','C','E'],
        ['S','F','C','S'],
        ['A','D','E','E']
        ]
        给定 word = "ABCCED", 返回 true
        给定 word = "SEE", 返回 true
        给定 word = "ABCB", 返回 false
*/

public class Solution79 {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)){
                    if (word.length() == 1) return true;
                    int count = 1;
                    int[][] ints = new int[m][n];
                    ints[i][j] = 1;
                    if (method(i,j,word,count,board,m,n,ints)) return true;
                }
            }

        }
        return false;
    }

    private boolean method(int i, int j, String word, int count, char[][] board, int m, int n, int[][] ints) {
        if (count >= word.length() ){
            return true;
        }
        if ( i>=1 && ints[i-1][j] != 1 && board[i-1][j] == word.charAt(count)){
            count++;
            ints[i-1][j] = 1;
            if (method(i-1,j,word,count,board, m, n, ints)) return true;
            ints[i-1][j] = 0;
            count--;
        }
        if (i+1< m && ints[i+1][j] != 1 && board[i+1][j] == word.charAt(count)){
            count++;
            ints[i+1][j] = 1;
            if(method(i+1,j,word,count,board, m, n, ints)) return true;
            ints[i+1][j] = 0;
            count--;
        }
        if ( j>=1 && ints[i][j-1] != 1 && board[i][j-1] == word.charAt(count)){
            count++;
            ints[i][j-1] = 1;
            if (method(i,j-1,word,count,board, m, n, ints)) return true;
            ints[i][j-1] = 0;
            count--;
        }
        if (j+1< n  && ints[i][j+1] != 1&& board[i][j+1] == word.charAt(count)){
            count++;
            ints[i][j+1] = 1;
            if (method(i,j+1,word,count,board, m, n, ints)) return true;
            ints[i][j+1] = 0;
            count--;
        }
        return false;
    }
    @Test
    public void test(){
        boolean b = exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED");
        System.out.println(b);


    }
}
